package day02;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/2 20:14
 * 力扣 234
 */
public class LinkedListPractice09 {

    public boolean isPalindrome(ListNode head) {
        if (head.next == null) return true;
        ListNode middleNode = middle(head);
        ListNode compareList = reverseList(middleNode);
        while(compareList != null) {
            if (compareList.val != head.val) {
                return false;
            }
            head = head.next;
            compareList = compareList.next;
        }
        return true;
    }


    /**
     * 找到中间节点
     * @param head
     * @return
     */
    private ListNode middle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 没有走到链表结尾
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        ListNode newList = null;
        while(head != null) {
            ListNode p = head.next;
            head.next = newList;
            newList = head;
            head = p;
        }
        return newList;
    }

}
